package random;

import java.util.Arrays;

/**
 * 雪糕的最大数量
 *
 * 商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。
 * Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。
 * 给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。
 */

public class L1833 {

    public static void main(String[] args) {
        System.out.println(new L1833().maxIceCream(new int[]{1,6,3,1,2,5}, 20));
    }

    /**
     * 排序 + 贪心算法
     */
    public int maxIceCream(int[] costs, int coins) {
        Arrays.sort(costs);
        int count = 0;
        for (int cost : costs) {
            if (cost <= coins) {
                count++;
                coins -= cost;
            }else {
                break;
            }
        }
        return count;
    }


    /**
     * 计数排序 + 贪心
     */
    public int maxIceCream1(int[] costs, int coins) {
        int[] freq = new int[100001];
        for (int cost : costs) {
            freq[cost]++;
        }
        int count = 0;
        for (int i = 1; i <= 100000; i++) {
            if (coins >= i) {
                int curCount = Math.min(freq[i], coins / i);
                count += curCount;
                coins -= i * curCount;
            } else {
                break;
            }
        }
        return count;
    }

}
